章節名稱: feasibility of learning

一 Learning is Impossible?

No Free Lunch

在某些情況我們可能無法學習到東西，這邊舉了個例子，我們用在資料內的 $x_n$ 、 $y_n$ ，來驗證產生出來的 $g$ 是否近似於 $f$ ，但就算資料內的都相符了，我們仍然無法確定 $g$ 是否近似於 $f$ ，綜觀來看好像沒學到東西。
圖中 $f_n$ 我們並不知道，所以資料外 ($D$) 的 $y_n$ 我們自然無法得知，也就無法保證一定學到了甚麼東西。

但實際上這類可能才是我們想要的，利用已知的資料來達到預測資料外的結果。

通常我們無法只丟資料，然後去學，來得知資料外的事。 => No Free Lunch
除非加上一些假設。

二 Probability to the Rescue

用機率來推論

所以由剛剛來看，我們需要一些東西來對未知的 $f$ 做一些推論。

我們想要知道瓶子裡，橘色彈珠的比例佔多少，除了一顆一顆數要如何知道呢？
我們可以用機率來推論:

罐子裡橘色的機率為 : $\mu$ (未知)

隨機抓一把彈珠 => Sample
Sample 裡橘色的機率為: $\nu$ (已知)

則我們能利用 in-sample $\nu$ 來得知 out-of-sample $\mu$ 的一些資訊，

首先，無法知道 一定 有多少比例的橘色，比如抓一把結果全都是綠，但實際上裡面有橘色。
我們可以知道的是 可能 $\nu$ 和 $\mu$ 是很接近的。

Hoeffding’s Inequality

而數學上如何說明這件事呢？

結論上來說就是當 N 很大時，$\mu$ 和 $\nu$ 會很接近的機率很大。也就是 $\mu$ 和 $\nu$ 相差很大的機率很小，寫成數學則像是圖中那樣。(exp: 指數函數，$e^x$ )

PAC : 有很大的機會 差不多 是對的。

而在 Hoeffding’s Inequality 中，首先要有合理的 N 和 $\epsilon$ (容忍度) ，然後我們不需要知道 $\mu$。
當 N 或是 $\epsilon$ 越大時，圖中不等式右邊的值就越小。

練習

$$\epsilon = \mu - \nu = 0.3 \\ \Bbb{P}[ \vert \nu - \mu \vert \gt \epsilon ] \le 2 \times e^{(-2 \times {\epsilon}^2 \times 10)} \fallingdotseq 0.33$$

此答案對所有 $\mu$ 皆可以，有過度的空間(overestimate)，也就是所謂的上限。

至於實際機率則要利用 $\mu$ 才能算出來，答案是 4 ，查了一下，算法如下:

首先 $\nu \le 0.1$ ，代表 所選的 10 顆內(Sample)，有可能有 1顆(0.1) 或 0顆(0) 橘的。
而在瓶子(Population) 內發生這樣的機率為:
($\mu$ 為挑到橘色的機率)

• 0 顆橘的 ${(1-\mu)}^{10} = {0.6}^{10}$
• 1 顆橘的 ${ 10 \choose 1 } \times {0.4}^1 \times {0.6}^9$

兩個相加:
${0.6}^{10} + { 10 \choose 1 } \times {0.4}^1 \times {0.6}^9 = 0.04635\ldots \fallingdotseq 0.05$